package leetcodev1.数组;

public class LeetCode55 {

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;//
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    //动态规划
    //效率极低 没有看准一个规律->可以都调到x，就肯定可以跳过x以内的所有格子
    //因此只需要记录最大值即可
    public boolean canJump1(int[] nums) {
        int length = nums.length;
        int[] dict = new int[length];
        dict[0] = 1;//1是可达 0是不可达

        for (int i = 0; i < length; i++) {
            if (dict[i] == 1) {
                //更新该步骤可达的dict
                for (int j = 1; j <= nums[i]; j++) {
                    if (i + j < length) {
                        dict[i + j] = 1;
                    }
                }
            }
        }

        return dict[length - 1] != 0;
    }
}
